Leetcode-Search Insert Position

发表于 | 分类于 |

Search Insert Position

给定一个有序的无重复元素的序列，和一个目标元素，求出该元素在数组中的下标，若数组中不存在该元素，则返回其在数组中的顺序下标。
Description

解题思路：
直接采用暴力查询。首先判断目标元素是否在数组中，若存在，则直接返回下标。
若不存在，将目标元素与数组中的最大最小值比较；如果介于最大最小值之间，则与数组中的任意两个相邻元素进行比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if target in nums:
            return nums.index(target)
        
        if target<min(nums):
            return 0
        elif target>max(nums):
            return len(nums)
        else:
            for i in range(len(nums)):
                if nums[i]<target and nums[i+1]>target:
                    return i+1

改进：
采用二分查找的思路，leetcode上提供的另一种解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def searchInsert(self, nums, key):
    if key > nums[len(nums) - 1]:
        return len(nums)

    if key < nums[0]:
        return 0

    l, r = 0, len(nums) - 1
    while l <= r:
        m = (l + r)/2
        if nums[m] > key:
            r = m - 1
            if r >= 0:
                if nums[r] < key:
                    return r + 1
            else:
                return 0

        elif nums[m] < key:
            l = m + 1
            if l < len(nums):
                if nums[l] > key:
                    return l
            else:
                return len(nums)
        else:
            return m